package first.niuke.midding;

import java.util.HashMap;

/**
 * @ClassName NC12
 * @description:
 * @author: 荣燊
 * @create: 2021-04-11 20:03
 **/
public class NC12 {
    // 重建二叉树
    // 在前序数组中找根，中序数组中找左右树
    HashMap<Integer, Integer> map = new HashMap<>();
    int[] pre;

    public TreeNode reConstructBinaryTree(int[] pre,int[] in) {
        for (int i=0; i<in.length; i++) {
            map.put(in[i], i);
        }
        this.pre = pre;
        return recur(0, 0, in.length-1);
    }

    public TreeNode recur(int root, int left, int right) {
        if (left > right) {
            return null;
        }
        TreeNode node = new TreeNode(pre[root]);
        int i = map.get(pre[root]);

        node.left = recur(root+1, left, i-1);
        node.right = recur(root+1+(i-1-left+1), i+1, right);

        return node;
    }

    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int root) {

        }
    }
}
